/**
 * 493. 翻转对
 * https://leetcode-cn.com/problems/reverse-pairs/
 */
public class Solutions_493 {
    public static void main(String[] args) {
//        int[] nums = {2, 4, 3, 5, 1};  // output: 3
//        int[] nums = {1, 3, 2, 3, 1};  // output: 2
//        int[] nums = {5, 4, 3, 2, 1};  // output: 4
        int[] nums = {2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647};  // output: 0

        int result = reversePairs(nums);
        System.out.println(result);
    }

    public static int reversePairs(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        return sort(nums, 0, nums.length - 1);
    }

    /**
     * 完成 [left, right] 区间的元素分解、再合并
     * @param nums 数组
     * @param left 起始索引
     * @param right 结束索引
     * @return 区间中的翻转对数量
     */
    public static int sort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        // 计算出 mid，划分出左右两部分
        int mid = left + (right - left) / 2;

        int leftRes = sort(nums, left, mid);
        int rightRes = sort(nums, mid + 1, right);
        return leftRes + rightRes + merge(nums, left, mid, right);
    }

    /**
     * [2, 3, 4] [1, 5]
     * 合并 [left, mid], [mid + 1, right] 两区间的过程中，完成翻转对数量的计算，同时排序元素
     * @param nums 数组
     * @param left 左区间开始索引
     * @param mid 左区间结束索引
     * @param right 右区间结束索引
     * @return [left, mid], [mid + 1, right] 两区间的元素
     */
    public static int merge(int[] nums, int left, int mid, int right) {
        // 排序完成的元素，记录到 arr 数组中
        int res = 0;
        // 不直接使用 left，mid 变量，因为后面还需要用到
        int l = left, m = mid + 1;
        // 计算翻转对
        while (l <= mid && m <= right) {
            // 需要转化成 long 值
            long n = (long)nums[m] * 2;
            if (nums[l] > n) {
                // 既然 nums[l] > nums[m] * 2 了，那么左区间中索引 l 之后的（大于等于 nums[l]）的元素，也一定是大于 nums[m] * 2 了
                res += mid - l + 1;
                // 右侧区间索引右移，继续判断 nums[l] > nums[m] * 2
                m++;
            } else {
                // 左侧区间索引右移，继续判断 nums[l] > nums[m] * 2
                l++;
            }
        }

        // 两个区间中的元素进行排序，
        int[] arr = new int[right - left + 1];
        int idx = 0;
        l = left;
        m = mid + 1;
        while (l <= mid && m <= right) {
            // 先记录较小值
            if (nums[l] <= nums[m]) {
                arr[idx] = nums[l];
                l++;
            } else {
                arr[idx] = nums[m];
                m++;
            }
            idx ++;
        }
        while (l <= mid) {
            // 左区间元素未添加完
            arr[idx] = nums[l];
            idx ++;
            l ++;
        }
        while (m <= right) {
            // 右区间元素未添加完
            arr[idx] = nums[m];
            idx ++;
            m ++;
        }
        // 替换到 nums 中
        for (int num : arr) {
            nums[left++] = num;
        }
        return res;
    }
}
